#include<iostream>
using namespace std;
template <class T1,class T2> void ShellInsert(T1 r[],T2 n);
template <class T>int length(T &arr);
template <class T>void print(T &arr);
int main()
{
    int a[]={6,4,2,7,61,4,2,72,4,2,7,6,4,2,75,2,7,61,4,2,72,4,2,7,6,4};
    ShellInsert(a,length(a));
    print(a);
}
//希尔排序
template <class T1,class T2> void ShellInsert(T1 r[],T2 n)
{
    for (int d = n/2; d>=1; d=d/2)
    {
        for (int i = d+1; i < n; i++)
        {
            if (r[i]<r[i-d])
            {
                r[0]=r[i];
                for(int j=i-d;j>0&&r[0]<r[j];j=j-d)
                {
                    r[j+d]=r[j];
                }
                r[j+d]=r[0];
            }
        }
    }
}
//计算数组长度
template <class T>int length(T &arr)
{
    return sizeof(arr)/sizeof(arr[0]);
}
//打印数组元素
template <class T>void print(T &arr)
{
    for (int i = 0; i < length(arr); i++)
    {
        cout<<arr[i]<<" ";
    }
    cout<<endl;
}